李智慧 高并发架构实战课（二）

07 | 海量数据处理技术回顾:为什么分布式会遇到 CAP 难题?

因为相对于“无状态”(stateless)的计算逻辑(可执行程序)，数据存储是“有状态”(stateful)的。

海量数据存储的核心问题包括:如何利用分布式服务器集群实现海量数据的统一存储?如何正确选择服务器写入并读取数据?为了保证数据的高可用性，如何实现数据的多备份存储?数据多备份存储的时候，又如何保证数据的一致性?

HDFS

HDFS，即 Hadoop 分布式文件系统，其架构如下。

HDFS 的关键组件有两个，一个是 NameNode，另一个是 DataNode。
NameNode 负责整个分布式文件系统的元数据管理，也就是文件路径名、访问权限、数据 块 ID、存储位置等信息。而 DataNode 负责文件数据的存储和读写操作，HDFS 将文件数 据分割成若干数据块(Block)，每个 DataNode 存储一部分数据块，这样文件就分布存 储在了整个 HDFS 服务器集群中。

HDFS 为了高可用，会将一个数据块复制为多份(缺省情况为 3 份)，并将多 份相同的数据块存储在不同的服务器上，甚至不同的机架上。

HDFS 的典型应用场景是大数据计算，即使用 MapReduce、Spark 这样的计算框架来计 算存储在 HDFS 上的数据。但是作为一个经典的分布式文件系统，我们也可以把 HDFS 用 于海量文件数据的存储与访问。

分布式关系数据库

可以使用分布式关系数据库中间件来解决这个问题，在中间件中完成数据的分片逻 辑，这样对应用程序是透明的。我们常用的分布式关系数据库中间件是 MyCAT，原理如下图。

MyCAT 是针对 MySQL 数据库设计的，应用程序可以像使用 MySQL 数据库一样连接 MYCAT，提交 SQL 命令。MyCAT 在收到 SQL 命令以后，查找配置的分片逻辑规则。

HBase

HBase 架构如下。

HRegion 是 HBase 中负责数据存储的主要进程，应用程序对数据的读写操作都是通过和 HRetion 通信完成的。

HBase 的设计重点就是 HRegion 的分布式。HRegionServer 是物理服务器，这些服 务器构成一个分布式集群，每个 HRegionServer 上可以启动多个 HRegion 实例。当一个 HRegion 中写入的数据太多，达到配置的阈值时，一个 HRegion 会分裂成两个 HRegion，并将 HRegion 在整个集群中进行迁移，以使 HRegionServer 的负载均衡，进 而实现 HRegion 的分布式。

应用程序要 先访问 HMaster 服务器，得到数据 key 所在的 HRegion 信息，再访问对应的 HRegion 获取数据。为了保证 HMaster 的高可用，HBase 会启动多个 HMaster，并通过 ZooKeeper 选举出一个主服务器。

ZooKeeper

CAP 原理认为，一个提供数据服务的分布式系统无法同时满足数据一致性 (Consistency)、可用性(Availibility)、分区耐受性(Patition Tolerance)这三个条件。

由于互联网对高可用的追求，大多数分布式存储系统选择可用性，而放松对一致性的要 求。而 ZooKeeper 则是一个保证数据一致性的分布式系统，它主要通过一个 ZAB 算法 (Zookeeper Atomic Broadcast， Zookeeper 原子广播)实现数据一致性，算法过程如 下。

布隆过滤器

布隆过滤器首先开辟一块巨大的连续内存空间，并将这个空间所有比特位都设置为 0。然后对每个 MD5 使用多种 Hash 算法，比如使用 8 种 Hash 算法，分别计算 8 个 Hash 值，并保证 每个 Hash 值是落在这个 1600G 的空间里的，也就是，每个 Hash 值对应 1600G 空间里的一个地址下标。然后根据计算出来的 Hash 值将对应的地址空间里的比特值设为 1，这 样一个 MD5 就可以将 8 个比特位设置为 1。

08 | 秒杀系统设计:你的系统可以应对万人抢购盛况吗?

Apollo 的核心挑战是:如何应对突然出现的数百倍高并发访问压力，并保 证用户只有在秒杀开始时才能下单购买秒杀商品?

需求分析

Apollo 的需求主要有两点。

  • 独立开发部署秒杀系统，避免影响现有系统和业务
    • 秒杀业务不能使用正常的电商业务流程，也不能和正常的网站交易业务共用服务器，甚至域名也需要使用自己独立的域名。
  • 防止跳过秒杀页面直接下单
    • 在此时间点之前，只能浏览 商品信息，不能下单。避免拿到URL提前下单

概要设计

Apollo 要解决的核心问题有:

  1. 如何设计一个独立于原有电子商务系统的秒杀系统，并独立部署。
  2. 这个秒杀系统如何承受比正常情况高数百倍的高并发访问压力。
  3. 如何防止跳过秒杀页面获得下单 URL。 我们将讨论这三个问题的解决方案，并设计秒杀系统部署模型。

独立秒杀系统页面设计

秒杀系统的流量控制

缓存是提高响应速度、降低服务器负载压力的重要手段。Apollo 采用多级缓存方案，可以更有效地降低服务器的负载压力。

  • 首先，浏览器尽可能在本地缓存当前页面，页面本身的 HTML、JavaScript、CSS、图片等 内容全部开启浏览器缓存。
  • 其次，秒杀系统还使用 CDN 缓存。
  • 秒杀系统中提供 HTML、JavaScript、CSS、图片的静态资源服务器和提供商品浏览的秒杀商品服务器也要在本地开启缓存功能。

需要在用户提交订单时，检查是否已经有其他用户提交订单。

事实上，为了减轻下单页面服务器的负载压力，可以控制进入下单页面的入口，只有少数用户能进入下单页面，其他用户则直接进入秒杀结束页面。

秒杀商品页面购买按钮点亮方案设计与下单 URL 下发

需要在秒杀商品静态页面中加入一个特殊的 JavaScript 文件，这个 JavaScript 文件设置为不被任何地方缓存。秒杀未开始时，该 JavaScript 文件内容为空。当秒杀开始 时，定时任务会生成新的 JavaScript 文件内容，并推送到 JavaScript 服务器。

新的 JavaScript 文件包含了秒杀是否开始的标志和下单页面 URL 的随机数参数。

这个 JavaScript 文件还有一个优点，那就是它本身非常小，即使每次浏览器刷新都访问 JavaScript 文件服务器，也不会对服务器集群和网络带宽造成太大压力。

秒杀系统部署模型


用户刷新页面时，除了特殊 JavaScript 文件，其他页面和资源文件都可以通过缓存获得。
下单 URL 中会包含一个随机数，这个随机数也会由定时任务推送给下单服务器，下单服务器收到用户请求的时候，检查请求中包含的随机数是否正确，即检查该请求是否是伪造的。

09 | 交友系统设计:哪种地理空间邻近算法更快?

Liao 面临的技术挑战包括:面对海量的用户，如何为其快速找到邻近的人，可以选择的地 理空间邻近算法有哪些?Liao 如何在这些算法中选择出最合适的那个?

需求分析

功能用例图如下

用户规模分析

Liao 的目标用户是全球范围内的中青年单身男女，预估目标用户超过 10 亿，系统按 10 亿 用户进行设计。

概要设计

采用典型的微服务架构设计方案，用户通过网关服务器访问具体的微服 务。

首先，用户所有请求都通过统一的网关服务器处理。网关服务器负责限流、 防攻击、用户身份识别及权限验证、微服务调用及数据聚合封装等，而真正的业务逻辑则 通过访问微服务来完成。

  • 用户微服务
  • 图片微服务
    • 我们使用 Nginx 作为图片服务器，图片服务器可以线性扩容，每写满一台 服务器(及其 Slave 服务器)，就继续写入下一台服务器。服务器 IP、图片路径则记录在 用户数据库中。同时，购买 CDN 服务，缓存热门的用户照片。
  • 配对微服务
    • 将数据发送给一个流式大数据引擎进行计算。
  • 推荐微服务：负责向用户展示其可能感兴趣的、邻近的用户
    • 一方面，推荐微服务需 要根据用户操作、个人兴趣、交友偏好调用协同过滤等推荐算法进行推荐，另一方面必须 保证推荐的用户在当前用户的附近。

详细设计

距离计算公式采用半正矢公式。

通常的空间邻近算法有以下 4 种，我们一一进行分析，最终选择出最合适的方案。

  • SQL 邻近算法（直接毙掉）
  • 地球网格临近算法
    • 我们可以将所有的网格及其包含的用户都记录在内存中。当我们进行邻近查询时，只需要 在内存中计算用户及其邻近的 8 个网格内的所有用户的距离即可。
  • 动态网格算法
    • 将 4 叉树所有的叶子节点顺序组成一个双向链表，每个节点在链表上的若 干个前驱和后继节点正好就是其地理位置邻近的节点。
    • 动态网格也叫 4 叉树网格，在空间邻近算法中较为常用，也能满足 Liao 的需求。但是编程实现稍稍有点麻烦，而且如果网格大小设计不合适，导致树的高度太高，每次查找需要遍历的路径太长，性能结果也比较差。
  • GeoHash 算法
    • redis 的 GeoHash 并不会直接用经、纬度做 key，而是采用一种基于 Z 阶曲线的 编码方式，将二维的经、纬度，转化为一维的二进制数字，再进行 base32 编码
    • 得到两个二进制数后，再将它们合并成一个二进制数。合并规则是，从第一位开始，奇数位为经度，偶数位为纬度
    • 在 Redis 中，需要面对更通用的地理位置计算场景，所以 Redis 中的 GeoHash 并没有用 Hash 表存储，而是用跳表存储。
      • 所谓的 Z 阶曲线布局，本质其实就是基于 GeoHash 的二进制排序。将这些经过 编码的 2 进制数据用跳表存储。查找用户的时候，可以快速找到该用户，沿着跳表前后检 索，得到的就是邻近的用户。

10 | 搜索引擎设计:信息搜索怎么避免大海捞针?

Bingoo 的主要技术挑战包括:

  1. 针对爬虫获取的海量数据，如何高效地进行数据管理;
  2. 当用户输入搜索词的时候，如何快速查找包含搜索词的网页内容;
  3. 如何对搜索结果的网页内容进行排序，使排在搜索结果列表前面的网页，正好是用户期 望看到的内容。

概要设计

一个完整的搜索引擎包括分布式爬虫、索引构造器、网页排名算法、搜索器等组成部分， Bingoo 的系统架构如下。

索引的构造主要通过索引构造器完成，索引构造器读取 HDFS 中 的网页内容，解压缩后提取网页中的单词，构建一个“docID-> 单词列表”的正排索引。 然后，索引构造器再根据这个正排索引构建一个“单词 ->docID 列表”的倒排索引
设计了 64 个索引桶，根据 docID 取模，将不同网页分配到不同的桶中，在每个桶中 分别进行索引构建，通过并行计算来加快索引处理速度。

详细设计

索引

首先，索引构造器将所有的网页都读取完，构建出所有的“docID-> 单词列表”正排索引。
然后遍历所有的正排索引，再按照“单词→docID 列表”的方式组织起来，就是倒排索引了。
拉链法

跳表实际上是在链表上构建多级索引，在索引上遍历可以跳过底层的部分数据，我们可以 利用这个特性实现链表的跳跃式比较，加快计算速度。使用跳表的交集计算时间复杂度大 约是 O(log(n))。

PageRank 排名算法

对于 N 个网页，任何一个页面 Pi 的 PageRank 计算公式如下:
公式中，Pj ∈ M (Pi ) 表示所有包含有 Pi 超链接的 Pj ，L(Pj ) 表示 Pj 页面包含的超链接 数，N 表示所有的网页总和。由于 Bingoo 要对全世界的网页进行排名，所以这里的 N 是 一个万亿级的数字。

11 | 反应式编程框架设计:如何使方法调用无阻塞等待?

反应式系统应该具备如下的 4 个特质。

  • 即时响应
  • 回弹性
    • 能够进行自我修复，保证正常 运行，保证响应，不会出现系统崩溃和宕机的情况。
  • 弹性
    • 能够自动伸缩以适应应用负载压力，根据压 力自动调整自身的处理能力，或者根据自身的处理能力，调整进入系统中的访问请求数量。
  • 消息驱动
    • 功能模块之间、服务之间通过消息进行驱动，以完成服务的流程。

目前主流的反应式编程框架有 RxJava、Reactor 等，它们的主要特点是基于观察者设计模式的异步编程方案，编程模型采用函数式编程。
反应式编程并不是必须用观察者模式和函数式编程。我们准备开发一个纯消息驱动，完全异步，支持命令式编程的反应式编程框架，框架名称为“Flower”。

需求分析

当并发用户请求到达应用服务器时，Web 容器线程不需要执行应用程序代码，它只是将用户的 HTTP 请求变为请求对象，将请求对象异步交给 Flower 框架的 Service 去处理，而 Web 容器线程自身立刻就返回。

概要设计

Flower 框架实现异步无阻塞，一方面是利用了 Java Web 容器的异步特性，主要是 Servlet3.0 以后提供的 AsyncContext，快速释放容器线程;另一方面则利用了异步的数据 库驱动和异步的网络通信，主要是 HttpAsyncClient 等异步通信组件。而 Flower 框架 内，核心应用代码之间的异步无阻塞调用，则是利用了 Akka 的 Actor 模型。
Akka Actor 的异步消息驱动实现如下。

Flower 框架的主要元素包括:Flower Service(服务)、Flower 流程和 Flower 容器。其 中，Service 实现一个细粒度的服务功能，Service 之间会通过 Message 关联，前一个 Service 的返回值(Message)，必须是后一个 Service 的输入参数(Message)。而 Flower 容器就负责在 Service 间传递 Massage，从而使 Service 按照业务逻辑编辑成一 个 Flow(流程)。

详细设计

Flower核心类图如下

Flower 框架核心关键类及其职责如下:

  1. Service 以及 HttpService 接口是框架的编程核心，开发者开发的 Service 需要实现 Service 或者 HttpService 接口。HttpService 与 Service 的不同在于 HttpService 在接口方法中传递 Web 参数，开发者利用 Web 接口可以将计算结果直接 print 到 HTTP 客户端;
  2. ServiceFactory 负责用户以及框架内置的 service 实例管理(加载 *.services 文件);
  3. ServiceFlow 负责流程管理(加载 *.flow 文件);
  4. ServiceActor 将 Service 封装到 Actor。

Flower 初始化及调用时序图如下。

第一个过程是服务流程初始化过程。首先，开发者通过 ServiceFacade 调用已经定义好的服务流程。然后，ServiceFacade 根据传入的 flow 名和 service 名，创建第一个 ServiceActor。这个 ServiceActor 将通过 ServiceFactory 来装 载 Service 实例，并通过 ServiceFlow 获得当前 Service 在流程中所配置的后续 Service(可能有多个)。依此递归，创建后续 Service 的 ServiceActor，并记录其对应的 ActorRef。

第二个过程是消息流处理过程。调用者发送给 ServiceFacade 的消息，会被 flow 流程中的第一个 ServiceActor 处理，这个 ServiceActor 会调用对应的 Service 实 例，并将 Service 实例的返回值作为消息发送给流程定义的后续 ServiceActor。

服务注册

开发者开发的服务需要在 Flower 中注册才可以调用，Flower 提供两种服务注册方式:配 置文件方式和编程方式。

流程编排

通过流程编排方式，实现服务间依赖

12 | 高性能架构的三板斧:分析系统性能问题从哪里入手?


其中，吞吐量 = 并发数 ÷ 响应时间

性能测试

  • 性能测试
    • 这个过程中，随着并发数的增加，吞吐 量也在增加，但是响应时间变化不大。系统正常情况下的并发访问压力应该都在这个范围内。
  • 负载测试
    • 这个过程中，随着并发数的增加，吞吐量只有小幅的增加，达到最大值后，吞吐量还会下降，而响应时间则会不断增加。
  • 压力测试
    • 到了系统崩溃点，吞吐量为 0，响应时间无穷大。

架构方面核心的优化思路有三个:通过分布式集群扩展系统的服务器，降低单一服务器的负载压力;通过缓存的方式降低系统的读负载压力;通过消息队列降低系统的写负载压力。对应的技术方案分别是:负载均衡、分布式缓存、消息队列，我称之为高性能架 构的三板斧。

负载均衡

应用层负载均衡通常用在规模比较小的集群上，而对于大规模的应用服务器集群， 我们使用 IP 层负载均衡或者链路层负载均衡。

IP 负载均衡不需要在 HTTP 协议层工作，可以在操作系统内核直接修改 IP 数据包的地址， 所以效率比应用层负载均衡高得多。

优化的方案就是采用链路层负载均衡。链路层负载均衡服务器并不修改请求数据包的 IP 地 址，而是修改数据链路层里的网卡 mac 地址，在数据链路层实现负载均衡。应用服务器返 回响应数据的时候，因为 IP 地址没有修改过，所以这个响应会直接到达用户的设备，而不 会再经过负载均衡服务器（目前大型互联网应用大多使用链路层负载均衡。）

分布式缓存

高并发架构中常见的分布式缓存有三种:CDN、反向代理和分布式对象缓存。

CDN(Content Delivery Network)即内容分发网络。目前很多互联网应用大约 80% 以上的网络流量都是通过 CDN 返回的。

反向代理则是 代理服务器，所有的网络请求都需要通过反向代理才能到达应用程序服务器。那么在这里 加一个缓存，尽快将数据返回给用户，而不是发送给应用服务器，这就是反向代理缓存。
一台服务器，既做反向代理服务器，也做负载均衡服务器。

CDN 和反向代理缓存对应用程序是透明的，通常被当做系统前端的一部分。而应用程序如 果要使用缓存，就需要分布式对象缓存。

缓存只能改善系统的读操作性能，对于写操作，缓存是无能为力的。我们不能把用户提交的数据直接写入缓存中，因为缓存通常被认为是一种不可靠的存储。

消息队列

优化写操作性能的主要手段是使用消息队列，将写操作异步化。

一方面，用户请求发送给消息队列就可以直接返回响应给用户了，
而消息队列服务器的处理速度要远远快于数据库，用户端的响应时间可以极大缩短;
另一方面，消息队列写数据库的时候，可以根据数据库的负载能力控制写入的速度，即使用户请求并发很高，也不会导致数据库崩溃，消息队列可以使系统运行在一个性能最优的负载压力范围内。